package com.just.fun.crazyStack;

import java.util.Stack;

/**
 * Created by han.yuan
 * 2018/4/9
 * 用栈实现中缀表达式转成后缀表达式
 */
public class StackTest {
    public static void main(String[] args) {
        String origin = "3+1*4/8+9*5";
        System.out.println("中缀表达式："+origin);
        System.out.println("后缀表达式："+toPostfix(origin));
    }

    /**
     * 转成后缀表达式
     *
     * @param str 原始字符串（中缀表达式）
     */
    public static String toPostfix(String str) {
        StringBuilder sb = new StringBuilder();
        //先转成一个数组，方便遍历
        char[] a = str.toCharArray();
        //定义一个栈
        Stack<String> stack = new Stack<>();
        char item;
        for (int i = 0; i < a.length; i++) {
            item = a[i];
            switch (item) {
                case '+':
                case '-': {
                    if (!stack.isEmpty()) {
                        //遇到优先级比自己高的，先把所有的出栈，然后入栈
                        //优先级同级的取栈顶
                     if(stack.peek().equals("*")||stack.peek().equals("/")){
                        while (!stack.isEmpty()) {
                            sb.append(stack.pop());
                        }

                     }else{
                         sb.append(stack.pop());
                     }
                    }
                    stack.push(String.valueOf(item));
                }
                break;
                case '*':
                case '/': {
                    if (!stack.isEmpty()) {
                        if (stack.peek().equals("*") || stack.peek().equals("/")) {
                            sb.append(stack.pop());
                        }
                    }
                    stack.push(String.valueOf(item));
                }
                break;
                default: {
                    sb.append(item);
                }
            }
        }
        if (!stack.isEmpty()) {
            while (!stack.isEmpty()) {
                sb.append(stack.peek());
                stack.pop();
            }
        }
        return sb.toString();
    }
}
